#include "SortClass.h"
#include<iostream>
#include<string>
using namespace std;
void swap(int& x, int& y) {
	x += y;
	y = x - y;
	x -= y;
}
void SortClass::bubblSort(int* num, int front,int rear) {
	for (int i = front; i < rear; i++)
		for (int j = i; j < rear - 1; j++)
			if (num[j] < num[j + 1])
				swap(num[j], num[j + 1]);
}
void SortClass::chooseSort(int* num, int front, int rear) {
	for (int i = front; i < rear - 1; i++)
		for (int j = i + 1; j < rear; j++)
			if (num[i] > num[j])
				swap(num[i], num[j]);
}
void SortClass::insertSort(int* num, int front, int rear) {
	for (int i = front; i <rear; i++)
	{
		int k = num[i];
		for (int j = i; j >= front; j--)
			if (j>front&&k > num[j - 1])
				num[j]=num[j - 1];
			else{
				num[j] = k;
				break;
		}
	}
}
void SortClass::quickSort(int* num, int front, int rear) {
	if (front >= rear)return;
	int i = front, j = rear, k = num[front];
	while (i < j) {
		while (i < j && num[j] >= k)j--;
		if (i < j)num[i++] = num[j];
		while (i<j && num[i]<k)i++;
		if (i < j)num[j--] = num[i];
	}
	num[i] = k;
	quickSort(num, front, i - 1);
	quickSort(num, i + 1, rear);
}
void SortClass::mergeSort(int* num, int front, int rear) {
	if (front >= rear)return;
	int mid = (front + rear) / 2;
	int b=front,e = mid + 1;
	mergeSort(num, front, mid);
	mergeSort(num, e, rear);
	int* arr = new int[rear - front];
	int i = 0,j=mid;
	while (true)
		if (b <= mid && e <= rear)
			if (num[b] >= num[e])arr[i++] = num[b++];
			else arr[i++] = num[e++];
		else if (b <= mid)arr[i++] = num[b++];
		else if (e <= rear)arr[i++] = num[e++];
		else break;
	for (int i = front; i <= rear; i++)
		num[i] = arr[i - front];
}
void SortClass::countSort(int* num, int front, int rear) {
	int Max = num[front], Min = num[front];
	for (int i = front; i < rear; i++) {
		Max = Max > num[i] ? Max : num[i];
		Min = Min < num[i] ? Min : num[i];
	}
	int d = Max - Min + 1;
	int* arr = new int[d];
	for (int i = 0; i < d; i++)
		arr[i] = 0;
	for (int i = front; i < rear; i++)
		arr[num[i] - Min]++;
	int n = 0;
	for(int i=0;i<d;i++)
		if (arr[i] > 0) {
			num[n++] = i + Min;
			arr[i--]--;
		}
}